package com.zjj.algorithm.learning.dmsxl.dynamicplan;

/**
 * 70. 爬楼梯 简单题
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 * <p>
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：n = 2
 * 输出：2
 * 解释：有两种方法可以爬到楼顶。
 * 1. 1 阶 + 1 阶
 * 2. 2 阶
 * 示例 2：
 * <p>
 * 输入：n = 3
 * 输出：3
 * 解释：有三种方法可以爬到楼顶。
 * 1. 1 阶 + 1 阶 + 1 阶
 * 2. 1 阶 + 2 阶
 * 3. 2 阶 + 1 阶
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= n <= 45
 *
 * @author zjj_admin
 * @date 2022/12/22 15:53
 */
public class DynamicPlan_03_ClimbingStairs {

    public static void main(String[] args) {
        int res = climbStairs(16);
        System.out.println("res = " + res);
    }

    /**
     * 从dp[i]的定义可以看出，dp[i] 可以有两个方向推出来。
     * <p>
     * 首先是dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶不就是dp[i]了么。
     * <p>
     * 还有就是dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶不就是dp[i]了么。
     * <p>
     * 那么dp[i]就是 dp[i - 1]与dp[i - 2]之和！
     * <p>
     * 所以dp[i] = dp[i - 1] + dp[i - 2] 。
     * <p>
     * 时间
     * 0 ms
     * 击败
     * 100%
     * 内存
     * 38.4 MB
     * 击败
     * 38.22%
     *
     * @param n
     * @return
     */
    public static int climbStairs(int n) {
        if (n <= 3) {
            return n;
        }
        int num1 = 2;
        int num2 = 3;
        int num = 0;
        for (int i = 4; i <= n; i++) {
            num = num1 + num2;
            num1 = num2;
            num2 = num;
        }
        return num;
    }
}
